package LimitedTimeGame.Day_0217;

/**
 * @author zxc
 * @date 2023/02/17 15:50
 **/
/**
 * 题目 ：数值的整数次方
 * 题目详述 ：
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 *
 * 提示：
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * -104 <= xn <= 104
 *
 */
public class MyPow02 {
    /**
     * 思路 ：
     * 递归，去求取pow(x,n)的前一个pow(x,n/2);
     * ===>
     * 快速幂 + 递归,来实现当前数x的幂运算;
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        // 特殊情况 ：若是n == 0的话，则无论n为何值，其幂运算的结果都是1;
        if(n == 0){
            return 1;
        }
        // 递归获取当前数x的幂运算结果;
        /**
         * 即，若是要求x^n的话，则只需要知道x^(n/2)
         * （1）若是n为奇数的话，则 x^n == x^(n/2) * x^(n/2) * x;
         * ===》 即，需要额外乘上一个x;
         * （2）若是n为偶数的话，则 x^n == x^(n/2) * x^(n/2);
         * 同时，需要注意的是，
         * （3）若是n > 0的话，则直接求解出 x^n 的值即可;
         * （4）若是n < 0的话，则需要对于求解出的 x^n的值，进行 1 / x^n 的操作即可;
         */
        return n > 0 ? recursion(x , n) : 1 / recursion(x , n);
    }

    private double recursion(double x, int n) {
        if(n == 0){
            return 1;
        }
        // 即，使用变量result，来存储 x^(n/2)的结果;
        double result = recursion(x , n / 2);
        return (Math.abs(n % 2) == 1) ? (result * result * x) : (result * result);
    }
    /**
     * 分析 ：
     * ===》
     * 即，若是采用递归去计算当前pow(x,n)的话，
     * （1）所需要的时间复杂度 ：O（logn）;
     * （2）同时，需要O（logn）的递归栈空间;
     */
}
